package com.zhang;

import java.util.*;

/**
 * @author ZhangJiXin
 * @Description 通用性的并查集
 * @date 2021/5/3 8:46
 */
public class GenericUnionFind<E>{
    private Map<E , Node<E>> parents;

    public GenericUnionFind() {
        this.parents = new HashMap<>();
    }

    /**
     * 存入元素
     * @Author ZhangJiXin
     * @Date 2021/5/4 8:32
     * @param v:
     * @return: void
     */
    public void setElement(E v){
        elementCheck(v);
        parents.put(v, new Node<>(v));
    }

    /**
     * 查询元素的根元素 如果为空则返回null
     * @Author ZhangJiXin
     * @Date 2021/5/4 8:33
     * @param v:  如果为空 则返回null
     * @return: E
     */
    public E find(E v){
        Node<E> node = findNode(v);
        return node == null ? null : node.element;
    }

    /**
     * 查询当前节点的根节点
     * @param v
     * @return 如果为空则返回null
     */
    private Node<E> findNode(E v) {
        Node<E> node = parents.get(v);

        if (node == null){
            return null;
        }
        int height = 0;
        while (!Objects.equals(node.parent.element,node.element)){
            node.parent = node.parent.parent;
            node = node.parent;
            height++;
        }
        node.height -= height;

        return node;
    }

    /**
     * 将两个元素的根节点合并 如果其中一个元素为空 或者根节点是同一个节点 则直接返回
     * @Author ZhangJiXin
     * @Date 2021/5/4 8:35
     * @param v1:
     * @param v2:
     * @return: void
     */
    public void union(E v1, E v2) {
        Node<E> node1 = findNode(v1);
        Node<E> node2 = findNode(v2);

        if (node1 == null || node2 == null){
            return;
        }

        if (Objects.equals(node1.element, node2.element)){
            return;
        }

        if (node1.height < node2.height){
            node1.parent = node2;
        }else if (node2.height < node1.height){
            node2.parent = node1;
        }else {
            node1.parent = node2.parent;
            node2.height++;
        }
    }

    /**
     * 判断两个元素的根节点是否是同一个根节点
     * @Author ZhangJiXin
     * @Date 2021/5/4 8:36
     * @param v1:
     * @param v2:
     * @return: boolean
     */
    public boolean isSame(E v1,E v2){
        return Objects.equals(find(v1),find(v2));
    }


    /**
     * 元素检查 元素不能为空 否则会报异常
     * @Author ZhangJiXin
     * @Date 2021/5/3 10:21
     * @param v:
     * @return: void
     */
    private void elementCheck(E v){
        if (v == null){
            throw new IllegalArgumentException("element must be not null");
        }
    }

    /**
     * 节点元素 用于存储元素 和父节点 高度
     * @Author ZhangJiXin
     * @Date 2021/5/4 8:36
     * @return: null
     */
    private class Node<V>{
        V element;
        Node<V> parent = this;
        int height = 1;

        public Node(V element){
            this.element = element;
        }
    }
}
